package com.leetcode.partition9;

import java.util.Arrays;
import java.util.LinkedList;

public class LC851喧闹和富有 {

    public static int[] loudAndRich(int[][] richer, int[] quiet) {
        return topological(richer, quiet);
    }

    public static void main(String[] args) {
        int[][] richer = {{1, 0}, {2, 1}, {3, 1}, {5, 3}, {4, 3}, {6, 3}, {3, 7}};
        int[] quiet = {3, 2, 5, 4, 6, 1, 7, 0};
        System.out.println(Arrays.toString(loudAndRich(richer, quiet)));
    }

    private static int[] topological(int[][] richer, int[] quiet) {
        int n = quiet.length;
        //根据richer建立邻接矩阵
        int[][] matrix = new int[n][n];
        int[] answer = new int[n], inDegree = new int[n];
        for (int i = 0; i < n; i++) answer[i] = i;
        for (int[] rich : richer) {
            matrix[rich[0]][rich[1]] = 1;
            inDegree[rich[1]]++;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        //将所有入度为0的结点入队
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) queue.addLast(i);
        }
        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            //遍历其边指向的邻结点，并尝试根据quiet来更新answer
            for (int v = 0; v < n; v++) {
                if (matrix[u][v] == 0) continue;
                //移除了u结点，结点v的入度就减少1，如果入度为0则进行入队，同时查看u是否能更新answer[v]
                if (quiet[answer[u]] < quiet[answer[v]]) answer[v] = answer[u];
                inDegree[v]--;
                if (inDegree[v] == 0) queue.addLast(v);
            }
        }
        return answer;
    }
}